package leetcode;

public class LeetCode64 {

    //递归超出时间限制
    private int result = Integer.MAX_VALUE, m, n;

    private int[][] dict;

    public int minPathSum1(int[][] grid) {
        dict = grid;
        m = dict.length;
        n = dict[0].length;
        walk(0, 0, 0);
        return result;
    }

    private void walk(int row, int column, int sum) {
        sum += dict[row][column];
        if (row == m - 1 && column == n - 1) {
            result = Math.min(result, sum);
            return;
        }
        if (row < m - 1)
            walk(row + 1, column, sum);
        if (column < n - 1)
            walk(row, column + 1, sum);
    }
//------------------------------------------------------------------

    int[][] dictArray;

    public int calculate(int[][] grid, int i, int j) {
        if (i == grid.length || j == grid[0].length) return Integer.MAX_VALUE;
        if (i == grid.length - 1 && j == grid[0].length - 1) return grid[i][j];
        if (dictArray[i][j] == 0)
            dictArray[i][j] = grid[i][j] + Math.min(calculate(grid, i + 1, j), calculate(grid, i, j + 1));
        return dictArray[i][j];
    }

    public int minPathSum(int[][] grid) {
        dictArray = new int[grid.length][grid[0].length];
        return calculate(grid, 0, 0);
    }

//------------------------------------------------------------------

}
